Mathematical foundation for graph structures
- A graph G is formally defined as an ordered pair G = (V, E), where V is the set of vertices (or nodes) and E is the collection of edges connecting pairs of vertices. This abstract definition applies to all graph types.
- For undirected graphs, each edge is an unordered pair written as $\{u, v\}$, meaning the connection has no inherent direction. For directed graphs (digraphs), edges are ordered pairs $(u, v)$ where the order matters—the edge points from u to v.
- A simple graph contains no self-loops (edges from a vertex to itself) and no parallel edges (multiple edges between the same pair of vertices). A multigraph relaxes these constraints, allowing multiple edges and potentially self-loops if specified.
- All modeling choices—direction, weights, multiplicity, whether loops are allowed—depend on the application. The formal definition provides the framework; we customize it based on what we need to represent in the real world.